1. Field of the Invention
The present invention relates to a data driven information processing device including a plurality of data driven processors, and a plurality of memory devices connected thereto. Particularly, the present invention relates to a method for verifying whether the paths between processors and the path between a processor and an image memory which is included as a memory device are properly connected, and a data driven processor for image processing and a data driven information processing device including such data driven processors suitable for that method.
2. Description of the Related Art
FIG. 1 shows a structure of the portion relating to one data driven processor of a conventional data driven information processing device for image processing, which is an example of a data driven information processing device. A similar system configuration example is disclosed in "An Evaluation of Parallel-Processing in the Dynamic Data-Driven Processor" (Proceedings on Microcomputer Architecture Symposium, Hiroshi Kanekura and Souichi Miyata, Japanese Society of Information Processing Engineers of Japan, Nov. 12, 1991).
Referring to FIG. 1, the data driven information processing device includes a data driven processor 10 and an image memory unit 12.
Data driven processor 10 includes input ports IA and IB connected to data transmission paths 14 and 16, respectively, output ports OA and OB connected to data transmission paths 18 and 20, respectively, an output port OV connected to a data transmission path 22 to image memory unit 12, and an input port IV connected to a data transmission path 24 from image memory unit 12. The detailed structure of data driven processor 10 will be described afterwards. Data transmission paths 14, 16, 18, 20, 22, and 24 are paths for transmitting data packets. The configuration of a data packet will be described afterwards.
Image memory unit 12 includes a memory interface 30 and an image memory 32. Memory interface 30 and image memory 32 are connected to each other via a memory access control line 34.
Memory interface 30 includes an input port connected to data transmission path 22 and an output port connected to data transmission path 24. Memory interface 30 serves to access image memory 32 in response to an access request applied from processor 10 in the form of a data packet. Memory interface 30 updates the contents of image memory 32, or reads out the contents of image memory 32 and returns the result as a data packet to processor 10 via transmission path 24.
The data driven information processing device of FIG. 1 operates as follows. An input packet is applied to data driven processor 10 from data transmission path 14 or 16 via input port IA or IB. This input packet having a configuration which will be described afterwards includes a generation number which is allocated according to the input time sequence. Data driven processor 10 for image processing has prestored preselected processing scheme. Data driven processor 10 carries out a process on an input data packet according to the scheme.
If access to image memory 32 (reference/update or the like on the contents of the image memory) is required in the process of the input packet, data driven processor 10 transmits a data packet through data transmission path 22 to carry out an access request to memory interface 30.
Memory interface 30 accesses image memory 32 through memory access control line 34. Memory interface 30 returns the result of access to data driven processor 10 by applying the resultant data packet to input port IV of data driven type processor 10 via data transmission line 24.
Data driven processor 10 for image processing provides an output packet to one of data transmission paths 18 and 20 via either output port OA or OB when the process on the input packet ends.
FIG. 2 shows the field configuration of a data packet 40 provided from data driven processor 10 to memory interface 30 via data transmission path 22. Referring to FIG. 2, data packet 40 includes an instruction code 42 of 8 bits, a generation number 44 of 24 bits, first data 46 of 12 bits, second data 48 of 12 bits, and a processor number 50 of 10 bits.
Instruction code 42 indicates the processing contents on image memory 32, such as reference or update of the contents of the image memory.
Generation number 44 is an identifier given to a data packet at the time it is applied to data driven processor 10 through data transmission path 14 or 16 (refer to FIG. 1) to form a time series according to the input sequence of data packets. The contents of this generation number 40 is used in data matching in data driven processor 10 for image processing (refer to FIG. 1). The generation number also serves as an address for the image memory with respect to memory interface 30 (FIG. 1). In accessing image memory 32, an address in image memory 32 to be accessed is determined according to generation number 44.
The meaning of first data 46 and second data 48 is determined according to the contents of instruction code 42. For example, when instruction code 42 indicates update of the contents of image memory 32, first data 46 is the data to be written into image memory 32, and second data 48 has no meaning. When instruction code 42 indicates reference to the contents of image memory 32, first and second data 46 and 48 both have no meaning.
Processor number 50 is data for specifying a particular data driven processor 10 out of a plurality of data driven processors. Data driven processor 10 carries out a process determined by instruction code 42 on data packet 40 when processor number 50 in data packet 40 applied via data transmission path 14 or 16 matches its own allocated processor number. When processor number 50 does not match its own allocated processor number, data driven processor 10 directly outputs the data packet through either output port OA or OB according to a scheme described afterwards.
FIG. 3 shows the field configuration of a data packet 60 returned to data driven processor 10 from memory interface 30 (refer to FIG. 1) via data transmission path 24. The field configuration of data packet 60 is identical to that of the data packets transmitted through data transmission paths 14, 16, 18 and 20 shown in FIG. 1.
In FIG. 3, instruction code 62, generation number 64, and processor number 68 are similar to instruction code 42, generation number 44, and processor number 50 shown in FIG. 2. First data 66 contains 12 bits. Data indicating the result may be stored in first data 66 depending upon the type of processing on image memory 32.
FIG. 4 is a block diagram of a data driven information processing device in which four data driven processors 10 for image processing and four image memory units 12 shown in FIG. 1 are employed. Referring to FIG. 4, this data driven information processing device includes two hosts 70 and 72, and four data driven processors PE#0-PE#3 connected in a network so that each processor can be reached from another arbitrary processor. Each of data driven processors PE#0-PE#3 has a structure identical to that of data driven processor 10 of FIG. 1. Image memory units VM#0-VM#3 are connected to data driven processors PE#0-PE#3, respectively. The structure of each of image memory units VM#0-VM#3 is identical to that of memory unit 12 shown in FIG. 1. The connection between a data driven processor and a corresponding image memory unit is similar to that between data driven processor 10 and image memory unit 12 shown in FIG. 1. It is to be noted that hosts 70 and 72 may be the same unitary host. This applies to all the embodiments of the invention of the present application.
The example shown in FIG. 4 has input port IA of processor PE#0 connected to one output of host 70. The other input port IB of processor PE#0 is connected to one output port OB of processor PE#2. One output port OA of processor PE#0 is connected to one input port IA of processor PE#2. The other output port OB of processor PE#0 is connected to one input port IA of processor PE#3.
One input port IA of processor PE#1 is connected to one output port OA of processor PE#3. The other input port IB of processor PE#1 is connected to the other output port of host 70. One output port OA of processor PE#1 is connected to input port IB of processor PE#2. The other output port OB of processor PE#1 is connected to input port IB of processor PE#3.
Output port OA of processor PE#2 is connected to one input port of host 72. Output port OB of processor PE#3 is connected to the other input port of host 72.
Image memory units VM#0, VM#1, VM#2, and VM#3 are connected to processors PE#0, PE#1, PE#2, and PE#3, respectively. This manner of connection is identical to the connection between processor 10 and image memory unit 12 shown in FIG. 1.
As mentioned above, any processor can reach another arbitrary processor according to the configuration shown in FIG. 4. For example, consider a case of transmitting a packet from processor PE#0 to processor PE#1. First, the packet is provided from output port OB of processor PE#0. This packet is applied to processor PE#3 via input port IA thereof. Processor PE#3 outputs this packet at output port OA, applying the packet to input port IA of processor PE#1. The communication of a data packet between other processors is carried out in a similar manner. However, it is to be noted that each data driven processor must identify whether an applied data packet is addressed to itself, and determine an output port from which that packet is output if not addressed to itself. This is accomplished as in the following.
FIG. 5 is a block diagram showing a structure of data driven processor 10 of FIG. 1. Referring to FIG. 5, a conventional data driven processor 10 for image processing includes an input processing unit 80, a junction unit 82, a main processing unit 84, a branch unit 86, an output processing unit 88, and a PE# register 90.
Input processing unit 80 includes two data packet inputs connected to input ports IA and IB, and two data packet outputs connected to the data packet input of branch unit 82 and one data packet input of output processing unit 88, respectively. The data packet to be processed by input processing unit 80 is 54 bits long here. Input processing unit 80 determines whether the data packet applied via data transmission path 14 or 16 is addressed to this data driven processor 10, and selectively provides the data packet to junction unit 82 or output processing unit 88 according to the determination result.
PE# register 90 serves to prestore a processor number allocated to data driven processor 10. This processor number is used for data packet distribution by input processing unit 80, and data packet branching by output branch unit 86.
Junction unit 82 includes a data packet input connected to one output of input processing unit 80, a data packet input connected to one data packet output of branch unit 86, and an output connected to the data packet input of main processing unit 84. Junction unit 82 merges the data packets provided from input processing unit 80 and the data packets sent from branch unit 86, and also detects corresponding data and provides to main processing unit 84 a complete data packet with all the required data.
Main processing unit 84 includes an input connected to data transmission path 24 via input port IV, an input connected to the output of junction unit 82, an output connected to data transmission path 22 via output port OV, and an output connected to the input of branch unit 86. Main processing unit 84 has a program stored in advance. Main processing unit 84 carries out a process according to the contents of the data packet provided from junction unit 82 to provide the resultant data packet to branch unit 86. When access to image memory 32 shown in FIG. 1 is required, main processing unit 84 sends the packet to image memory unit 12 via output port OV and data transmission path 22. Main processing unit 84 receives via data transmission path 24 and input port IV a data packet from image memory unit 12 having the access result of image memory 32 stored.
Branch unit 86 includes an input connected to the output of main processing unit 84, an output connected to the other input of output processing unit 88, and an output connected to one input of junction unit 82. Branch unit 86 can refer to the contents of PE# register 90. Branch unit 86 selectively provides a data packet to branch unit 82 or output processing unit 88 according to the processor number in the provided data packet and the contents of PE# register 90.
Output processing unit 88 includes two inputs connected to one output of input processing unit 84 and one output of branch unit 86, respectively, as described before, and two outputs connected to output ports OA and OB, respectively. Output processing unit 88 selects either output port OA or OB according to the processor number included in the applied data packet and the preset branching condition to provide the data packet to the selected output port.
An operation of data driven processor 10 of FIG. 5 will be described schematically hereinafter. A data packet is applied to input processing unit 80 via data transmission path 14 or 16. Input processing unit 80 compares the contents of PE# register 90 and the processor number of the input data packet. If they match, input processing unit 80 determines that this applied data packet is addressed to this data driven processor 10, and provides this data packet to junction unit 82 via one output. If they do not match, input processing unit 80 provides this data packet directly to output processing unit 88 via the other output.
Junction unit 82 merges data packets from branch unit 86 and data packets from input processing unit 80. Junction unit 82 detects paired data, and provides the data packet that is subjectable to data processing to main processing unit 84.
Main processing unit 84 carries out a predetermined process according to the instruction code in the applied data packet and provides the resultant data packet to branch unit 86 according to a prestored program. If access to image memory 34 is required, main processing unit 84 provides the processing packet to memory interface 30 via data transmission path 22, and then receives the resultant data packet via data transmission path 24. Instruction codes requiring access to image memory 32 are defined in advance as, for example, having "1" as the most significant bit. Whether access to image memory 32 is required or not can then be identified according to whether the most significant bit of the instruction code is "1" or not.
Branch unit 86 compares the processor number in the data packet applied from main processing unit 84 with the contents of PE# register 90, and provides the data packet to junction unit 82, if they match. Otherwise, branch unit 86 provides the data packet to output processing unit 88.
Output processing unit 88 selects either output port OA or OB according to the processor number in the data packet provided from branch unit 86 or input processing unit 80, and the preset branching condition related to that processor number. Output processing unit 88 provides the data packet to the selected data packet output port.
Proper connection between data driven processors, and between a data driven processor and an image memory unit must be established by respective predetermined paths for appropriate operation in the conventional data driven information processing device of the configuration shown in FIGS. 1-5. Erroneous operation of the system may originate from improper connection of the paths. In such a case, the defective path must be identified in order to take appropriate measures. However, to carry out a process of a higher level of complexity, the system complexity must be increased by increasing the number of processors and image memory units included in the data driven information processing device. The communication paths between processors and between a processor and image memory, and the number of combinations thereof will be appreciably increased as the number of processors and image memory units are increased, resulting in difficultly in the identification of the defective paths.
The process set forth in the following was conventionally carried out in order to identify a defective path or in order to verify whether path connection was carried out properly. A case of verifying the connection path between processors PE#0 and PE#2 in the system shown in FIG. 4, for example, is considered. In this case, as shown in FIG. 6, a predetermined data packet is generated in the host, and processing 100 is carried out to be applied to the system. The instruction code of the data packet applied to the system is a NOP instruction (NO Operation), and a bit pattern of "010101010101" is set as first data 66. It is assumed that the bit pattern of a NOP instruction is "00101000". This data packet is applied to processor PE#0 via input port IA of processor PE#0, as shown in FIG. 4.
Processor PE#0 provides this data packet from output port OA to input port IA of processor PE#2. Because the instruction code is a NOP instruction, no operation is carried out on the data packet by processor PE#0.
Similarly, processor PE#2 carries out no operation on the data packet, which is applied to host 72 via output port OA.
The output of a data packet to either output port OA or OB in each processor is determined according to preset conditions set forth in the following. Each output processing unit has a memory for storing in advance the branching condition of each processor. This memory has required values set by an initialization packet prior to application of a data packet. The values to be stored in the memory of an output processing unit by an initialization packet includes a mask value and a match value. A mask value and a match value have the following meanings. A logical product is taken between the processor number of a data packet applied to the output processing unit, and a mask value stored in the memory of the output processing unit. The result of the logical product is compared with the match value stored in the memory of the output processing unit. If both values match each other, the data packet is provided to output port OA, otherwise to output port OB. The selection of an output port in the verification of path connection is carried out in a similar manner.
Referring to FIG. 6, a NOP instruction 102 is carried out in processor PE#0, and a NOP instruction 104 is carried out in processor PE#2, followed by an output process 106 to the host. Because the instruction executed is only a NOP instruction, the contents of a data packet applied to host 72 should match that of the data packet provided from host 70. If the contents do not match each other, there is a possibility of a defective path.
It is assumed, for example, that the pattern of the first data region in the data packet output from host 70 is as described above, and the bit pattern of the first data region applied to host 72 is "1101010101". In this case, there is a possibility of a short circuit between the connection path corresponding to the most significant bit of the first data, and the connection path corresponding to an adjacent bit. Similarly, when the bit pattern of an instruction code of a data packet applied to host 72 differs from the bit pattern of the instruction code of the data packet output from host 70, there is a possibility of a defective connection path corresponding to an instruction code between the processors, or between the host and the processor.
The method of verifying the connection between a processor and an image memory in FIG. 7 is substantially similar. For example, consider the case of verifying the connection path between processors PE#0 and PE#2, and image memory units VM#0 and VM#2 connected thereto. Referring to FIG. 7, a predetermined data packet is generated in the host for verifying the connection with an image memory in the host, and a process 100A is carried out to be applied to the system. The instruction code of the data packet to be applied to the system is a VNOP instruction (Video NO Operation), and the bit pattern of "010101010101" is set in first data 66. It is assumed that the bit pattern of the VNOP instruction is "11010011". This data packet is applied to processor PE#0 via input port IO thereof as shown in FIG. 4.
Processor PE#0 provides this data packet from output port OV to the input port of image memory unit VM#0. Image memory unit VM#0 provides this data packet from the output port to input port IV of processor PE#0. Because the instruction code is a VNOP instruction, image memory unit VM#0 carries out no process on the data packet.
Processor PE#0 provides this data packet from output port OA to input port IA of processor PE#2.
Similarly, processor PE#2 carries out a process 104A executing a VNOP instruction as shown in FIG. 7. More specifically, processor PE#2 provides this data packet from output port OV to the input port of image memory unit VM#2. Image memory unit VM#2 provides this data packet from the output port to input port IV of processor PE#2. Because the instruction code is a VNOP instruction here, image memory unit VM#2 carries out no operation on the data packet.
Processor PE#2 carries out no process on the data packet, which is applied to host 72 via output port OA (step 106A in FIG. 7).
The output of a data packet to either output port OA or OB in each processor is carried out according to the aforementioned conditions.
Thus, as shown in FIG. 7, output process 106A is carried out for the host after a VNOP instruction 102A is carried out in processor PE#0 and image memory unit VM#0, and a VNOP instruction 104A in processor PE#2 and image memory unit VM#2. Because the instruction executed is only a VNOP instruction, the contents of the data packet input to host 72 should match the contents of the data packet output from host 70. If the contents do not match each other, there is a possibility of a defective path.
It is assumed that, for example, the bit pattern of the first data region of the data packet output from host 70 is as described above, and the bit pattern of the first data region of the data packet received by host 72 is "1101010101". In this case, there is a possibility of a short circuit between the connection path corresponding to the most significant bit of the first data and the connection path corresponding to an adjacent bit.
Conventional verification of a proper connection path of the entire system was carried out by sequentially verifying whether each connection path is proper or not.
However, it was extremely difficult, even impossible in some cases, to completely verify the connection of all paths by such a method in a conventional data driven information processing device. This is due to the fact that it is difficult to set an arbitrary bit pattern in each field of a data packet and apply that data packet to the device.
In setting the contents of a packet for path testing, an instruction code or the like corresponding to the bit pattern to be tested was selected by searching a prespecified preset instruction set. However, the following problems were encountered.
First, an instruction code corresponding to a desired bit pattern may be or may not be included in the current instruction set. For example, in one existing system, instruction codes corresponding to the bit patterns of "01110000"-"01111111" are not available. It is not possible to process a data packet including such an instruction code in processors. Therefore, testing of a connection path using such bit patterns could not be carried out.
Even if an instruction code corresponding to a bit pattern to be tested were available, that instruction code may be or may not be applicable for path testing. The reason is set forth in the following. Each processor carries out an operation on the input data to calculate output data according to the instruction code in the applied data packet. In many cases, the output data and the input data have different values. It is then extremely difficult to verify whether this difference is the result of the operation, or the results of a defective path connection. Furthermore, some instruction codes carry out operations in which output data take different values depending, not only on the values of the data in the input data packet, but also on the contents prestored in an accumulator or the like. If a bit pattern corresponding to such an instruction code is used for path connection testing, it will be necessary to set in advance, or confirm the contents of the accumulator or the like. It will then become more difficult to verify whether the contents of the output data properly indicates the operation result, or includes an error due to a defective path connection.
There is also the case where testing with a desired bit pattern cannot be carried out in the verification of a connection path with an image memory unit. In the above-described conventional example, the most significant bit of an instruction code requiring access to an image memory unit is always "1". Therefore, if an instruction code is used having a bit pattern in which the most significant bit is "0", that data packet cannot be output to the data transmission path leading to the image memory unit. It is therefore impossible to verify the path connection between a processor and an image memory unit using such an instruction code.
An extreme case will be described hereinafter. In an existing system, the instruction code corresponding to a bit pattern of "000100000" means "Discard input packet". Further, in the above-described conventional system, instruction codes corresponding to the bit patterns of "11100000"-"11101111" among the instructions that require access to an image memory unit also correspond to the function of discarding the data packet after operation. Therefore, even if a path connection test is carried out using these bit patterns, a data packet can not be output from the processor. In this case, it is almost impossible to identify by just the above-described testing whether an output packet was not obtained as a result of a process executed properly according to an instruction code of the input data packet, or as a result of a defective path connection.
Thus, it was not possible to verify path connection using an arbitrary bit pattern since the bit pattern of an instruction code included in a data packet that can be applied to the system was subjected to constraints of factors other than testing. It was therefore extremely difficult to verify the path connection. It is desirable to facilitate path connection with respect to various connections.